import numpy as np
from collections import deque
import networkx as nx
import itertools

# 初始化迷宫的四种走法
next_step = [[0, 1],  # 向右走
             [1, 0],  # 向下走
             [0, -1],  # 向左走
             [-1, 0]  # 向上走
             ]


def ExpandMapData(map):
    row = np.ones(19)
    col = np.ones((1, 21))
    out_data = map.copy()
    out_data = np.insert(out_data, 0, row, axis=0)
    out_data = np.insert(out_data, out_data.shape[0], row, axis=0)
    out_data = np.insert(out_data, 0, col, axis=1)
    out_data = np.insert(out_data, out_data.shape[1], col, axis=1)
    out_data[19, 0] = 0
    out_data[1, 20] = 0
    return out_data


def BFSearch(map, start_point, end_point):
    path_data = np.empty([map.shape[0], map.shape[1]], dtype=object)
    x = deque([])  # x 代表横坐标
    y = deque([])  # y 代表纵坐标
    s = deque([])  # s 代表步长
    head = 0
    tail = 0
    x.append(start_point[0])
    y.append(start_point[1])
    s.append(0)
    tail += 1
    point_data = {'x_pos': 0, 'y_pos': 0, 'length': 0, 'dir': None}
    path_data[start_point] = point_data
    flag = 0  # flag 是否达到终点，0表示没有，1表示达到
    while head < tail:
        for i in range(len(next_step)):
            next_x = x[head] + next_step[i][0]
            next_y = y[head] + next_step[i][1]

            if next_x < 0 or next_y < 0 or next_x >= len(map) or next_y >= len(map[0]):
                continue
            if path_data[next_x, next_y] is None and map[next_x, next_y] != 1:
                x.append(next_x)
                y.append(next_y)
                s.append(s[head] + 1)  # 分别追加到queue，步长逐渐累加
                point_data = {'x_pos': next_x, 'y_pos': next_y, 'length': s[head] + 1, 'dir': i}
                path_data[next_x, next_y] = point_data
                tail += 1
            if next_x == end_point[0] and next_y == end_point[1]:
                flag = 1
                break
        if flag == 1:
            break
        head += 1
    # print('The end of the x_queue:{}'.format(x))
    # print('The end of the y_queue:{}'.format(y))
    # print('The end of the s_queue:{}'.format(s))
    # print('The minimum of the path is: {0}'.format(s[tail - 1]))  # tail永远是指向下一个队列的值，所以要-1
    return s[tail - 1], path_data


def GetBFSPath(path_data, end_point):
    point = path_data[end_point]
    point_pos = end_point
    out_path = [end_point]
    while True:
        if 'dir' not in point or point['dir'] is None:
            break
        next_x = point['x_pos'] - next_step[point['dir']][0]
        next_y = point['y_pos'] - next_step[point['dir']][1]
        point = path_data[next_x, next_y]
        out_path.append((next_x, next_y))
    return out_path


def ParseShortestPath(map, targets, start_point, end_point):
    graph = nx.complete_graph(len(targets))
    for u, v in graph.edges():
        graph[u][v]['weight'], path = BFSearch(map, targets[u], targets[v])
        # 初始化最小权值路径和总权值
    min_weight_path = None
    min_weight = float('inf')

    # 遍历所有节点排列组合
    for permutation in itertools.permutations(graph.nodes()):
        weight = sum(graph[i][j]['weight'] for i, j in zip(permutation[:-1], permutation[1:]))
        if weight < min_weight:
            min_weight = weight
            min_weight_path = permutation

    print("最小权值路径:", min_weight_path)
    print("最小权值路径的总权值:", min_weight)

    positiveOrder = BFSearch(map, start_point, targets[min_weight_path[0]])[0] + \
                    BFSearch(map, end_point, targets[min_weight_path[-1]])[0]
    reverseOrder = BFSearch(map, start_point, targets[min_weight_path[-1]])[0] + \
                   BFSearch(map, end_point, targets[min_weight_path[0]])[0]
    if positiveOrder < reverseOrder:
        targets.insert(0, start_point)
        targets.append(end_point)
    else:
        targets.insert(0, end_point)
        targets.append(start_point)
        targets.reverse()

    return targets
